package com.ztom.hard;

/**
 * 数组中的逆序对
 * <p>
 * https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
 *
 * @author ZhangTao
 */
public class Code05ReversePairs {

    public int reversePairs(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        return process(nums, 0, nums.length - 1);
    }

    private int process(int[] nums, int l, int r) {
        if (l >= r) {
            return 0;
        }

        int mid = l + ((r - l) >> 1);
        return process(nums, l, mid)
                + process(nums, mid + 1, r)
                + merge(nums, l, mid, r);
    }

    private int merge(int[] nums, int l, int mid, int r) {
        int[] help = new int[r - l + 1];
        // 从后往前填
        int index = help.length - 1;
        int p1 = mid;
        int p2 = r;
        int count = 0;
        while (p1 >= l && p2 > mid) {
            // 归并前, 每组是有序的
            count += nums[p1] > nums[p2] ? p2 - mid : 0;
            help[index--] = nums[p1] > nums[p2] ? nums[p1--] : nums[p2--];
        }
        while (p1 >= l) {
            help[index--] = nums[p1--];
        }
        while (p2 > mid) {
            help[index--] = nums[p2--];
        }
        System.arraycopy(help, 0, nums, l, help.length);
        return count;
    }
}
